package com.shindo.base;

/**
 * 从数组中查找指定的字符,返回所在位置
 */
public class Array {
    public static void main(String[] args) {
        char[] arr = new char[]{'a', 'm', 'd', 'k', 'o'};
        char key = 'k';
        System.out.println(findByArr_1(arr, arr.length, key));
        System.out.println(findByArr_2(arr, arr.length, key));
    }

    /**
     * 方法一：遍历获取
     * 时间复杂度：O(n)
     */
    private static int findByArr_1(char[] arr, int n, char key) {
        if (null == arr || n < 0) {
            return -1;
        }

        int i = 0;
        while (i < n) {
            if (arr[i] == key) {
                return i;
            }
            ++i;
        }

        return -1;
    }

    /**
     * 在数字中，查找key，返回所在位置   --使用哨兵
     * 其中，n 表示数组 a 的长度
     * a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
     * a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
     *
     * @return
     */
    private static int findByArr_2(char[] arr, int n, char key) {
        if (null == arr || n < 0) {
            return -1;
        }

        // 因为后续要使用arr[n-1]来做哨兵，所以这里要提前判断
        if (arr[n - 1] == key) {
            return n - 1;
        }

        char tmp = arr[n - 1];
        arr[n - 1] = key;

        int i = 0;
        while (arr[i] != key) {
            ++i;
        }

        arr[n - 1] = tmp;

        //如果i == n-1 ,说明从0到n-1之间都没有找到key，否则i的位置就是key的位置
        if (i == n - 1) {
            return -1;
        } else {
            return i;
        }

    }

}
